package leet491incresesubseq

func IncreasingSubseq(nums []int) [][]int {
	// 思路和别的组合问题一样
	// 从一个指定子集中选择一个元素，但是不同的是，如果元素比path中的最新元素小的话就continue到下一个去了!!!
	result := [][]int{}
	path := []int{}

	var iterate func(start int)
	iterate = func(start int) {
		if start == len(nums) {
			return
		}
		used := []int{}
		for i := start; i < len(nums); i++ {
			// 当前层的去重遍历，应该是出现过就不再用了
			// 判断是否已经使用过，用used切片来记录
			if inSlice(used, nums[i]) {
				continue
			}
			used = append(used, nums[i])

			if len(path) == 0 || path[len(path)-1] <= nums[i] {
				path = append(path, nums[i])
			} else {
				continue
			}
			if len(path) >= 2 {
				pathCopy := make([]int, len(path))
				copy(pathCopy, path)
				result = append(result, pathCopy)
			}

			iterate(i + 1)
			// 迭代完后边的元素，要回退一下，以便每一轮遍历都是用相同的初始path
			path = path[:len(path)-1]
		}
	}
	iterate(0)
	return result
}

func inSlice(nums []int, value int) bool {
	for _, v := range nums {
		if v == value {
			return true
		}
	}
	return false
}
